"""
Problem 76: https://projecteuler.net/problem=76

Counting Summations

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two
positive integers?
"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/30
'''


def search():
    '''
    >>> assert search()==22
    '''
    count = 0
    m = 8
    for a1 in range(m//1+1):
        for a2 in range(m//2+1):
            for a3 in range(m//3+1):
                for a4 in range(m//4+1):
                    for a5 in range(m//5+1):
                        for a6 in range(m//6+1):
                            for a7 in range(m//7+1):
                                for a8 in range(m//8+1):
                                    if a1*1+a2*2+a3*3+a4*4+a5*5+a6*6+a7*7+a8*8 == 8:
                                        # print(str(count).zfill(2),'-->','1'*a1,'2'*a2,'3'*a3,'4'*a4,'5'*a5,'6'*a6,'7'*a7,'8'*a8)
                                        count += 1
    return count


CH = dict()  # {(money,minus):count}


def charge(money: int, minus: int):
    '''
    solutions can divide into 2 cases: with 1, without 1
        (1) with 1, have F(n-1) ways, where digit in [1,2,3,4,...]
        (2) without 1 , hav F'(n) ways, where digit in [2,3,4,...]
    F(n) = F(n-1) + F'(n)
    --> F(n) = F'(1) + F'(2) + F'(3) + ... + F'(n) 
        in other word, F'(n-k) means with 1*k, other digit in [2,3,4,...]

    >>> print(charge(1,1)-1)
    0
    >>> print(charge(2,1)-1)
    1
    >>> print(charge(3,1)-1)
    2
    >>> print(charge(5,1)-1)
    6
    >>> print(charge(8,1)-1)
    21
    '''

    if (money, minus) in CH:
        return CH[(money, minus)]

    if money == 0:
        CH[(money, minus)] = 1
        return 1

    k = money/minus

    if k < 1:
        CH[(money, minus)] = 0
        return 0

    if 1 <= k < 2:
        CH[(money, minus)] = 1
        return 1

    if k == 2:
        CH[(money, minus)] = 2
        return 2

    k = int(k)
    res = 0
    for i in range(k+1):
        CH[(money-i*minus, minus+1)] = charge(money-i*minus, minus+1)
        # print(f'charge({money-i*minus}, {minus+1}) = {CH[(money-i*minus, minus+1)]}')
        res += CH[(money-i*minus, minus+1)]

    CH[(money, minus)] = res
    return res


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(charge(100, 1)-1)
    # 190569291
